package homework1_array.alg_38;

import static homework1_array.Utils.printList;

public class ArrayHomework {

    public static void main(String[] args) {

        //todo 作业1：完成这个测试方法中的addByElementBySequence()方法
        arrayAddTest();

        // todo 作业2：完成这个测试类中的removeByElement()方法
        deleteTest();

    }

    /**
     * 在有序列表中插入元素
     */
    private static void arrayAddTest() {

        int[] arr = new int[20];
        arr[0] = 3;
        arr[1] = 4;
        arr[2] = 7;
        arr[3] = 8;
// 1.中间位置插入
        addByElementSequence(arr, 4, 6);
        printList("在有序数组的中间部分插入元素后的结果为：", arr, 5);
        //此时应输出 3 4 6 7 8

//2.尾部插入
        addByElementSequence(arr, 5, 9);
        printList("在有序数组的尾部插入元素后的结果为：", arr, 6);
        //此时应输出 3 4 6 7 8 9

//3.数组首部插入
        addByElementSequence(arr, 6, 1);
        printList("在有序数组的首部部分插入元素后的结果为：", arr, 7);
        //此时应输出：1 3 4 6 7 8 9

    }

    /**
     * 数组增加元素行为校验
     *
     * @param size 存储元素的数组
     * @param arr  指定的数组
     */
    public static void validArrAddAction(int[] arr, int size) throws Exception {
        if (size < 0) {
            throw new Exception("存储数量需要是非负数");
        }
        if (size >= arr.length) {
            throw new Exception("数组已满");
        }
    }

    //todo 作业1：完成这个方法

    /**
     * @param arr     存储元素的数组
     * @param size    数组中已经存储的元素数量
     * @param element 要插入数组的新元素
     * @return
     */
    public static void addByElementSequence(int[] arr, int size, int element) {
        try {
            //element插入位置的索引
            int insertIndex = -1;
            validArrAddAction(arr, size);
            //终止条件为i<size的 而不用arr.length的是 避免多余的无用的循环次数 因为很多时候数组不是满的
            for (int i = 0; i < size; i++) {
                //因为这是一个从小到大的有序数组 而且 还是从前往后遍历的 所以 element肯定比当前循环的前一个元素大
                //因此只要判断element比当前循环的值小 就可以确定插入位置了
                if (element < arr[i]) {
                    insertIndex = i;
                    break;
                }
            }
            //如果遍历完后 还是没有找到位置 那么就说明该元素是在末尾插入的
            //也因此此时不用移动其他数据 所以 直接在末尾插入就行了 然后 直接返回
            if (insertIndex == -1) {
                arr[size] = element;
                size++;
                return;
            }
            //移动插入位置之后的所有元素的位置(从后往前遍历是为了防止报数组索引越界)
            //arr[i] = arr[i+1]语句 需要判断当前元素是否是最后一个 否则的话会报数组索引越界异常
            for (int i = size; i > insertIndex; i--) {
                arr[i] = arr[i - 1];
            }
            //找到位置后以及移动完后 在将element变量值插入指定位置
            //该条语句一定要在最后一句执行 否则的话 会覆盖当前位置原来的值 导致 数据丢失
            arr[insertIndex] = element;
            size++;
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    /**
     * 删除测试
     */
    private static void deleteTest() {
        int[] arr = new int[]{2, 3, 4, 9, 10, 11, 12};

//1.删除头元素
        removeByElement(arr, 7, 2);
        printList("删除头元素后的结果为：", arr, 6);
        //此时应该打印 3 4 9 10 11 12

//2. 删除尾元素
        removeByElement(arr, 6, 12);
        printList("删除尾元素的结果为：", arr, 5);
        //此时应该打印 3 4 9 10 11

//3. 删除中间元素：
        removeByElement(arr, 5, 9);
        printList("删除尾元素的结果为：", arr, 4);
        //此时应该打印 3 4 10 11
    }

    /**
     * 从数组中删除元素e
     *
     * @param arr
     * @param size 数组已经存放的元素大小
     * @param key  要删除的元素
     */
    public static void removeByElement(int[] arr, int size, int key) {
        if (size > 0){
            int deleteIndex = -1;
            for (int i = 0; i < size; i++) {
                if (arr[i] == key) {
                    deleteIndex = i;
                    break;
                }
            }
            //说明当前数组中没有key元素 则不做任何动作
            if (deleteIndex == -1) {
                return;
            }

            //终止条件是i < size-1的原因是防止当前数组已经满的情况下 会报索引越界的问题
            for (int i = deleteIndex; i < size - 1; i++) {
                arr[i] = arr[i + 1];
            }
            //初始化最后一个元素
            arr[size - 1] = 0;
            size--;
        }
    }
}
